#include <stdio.h>

void swap(int a[], int i, int j)
{
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

void sort(int a[], int len)
{
    for(int end=len-1; end > 0; end--)
    {
        for(int begin=0; begin <= (int)((end-1)/2); begin++)
        {
            int max=begin;
            if (begin*2+1<=end && a[begin*2+1]>a[max])
            {
                max=begin*2+1;
            }
            if (begin*2+2<=end && a[begin*2+2]>a[max])
            {
                max=begin*2+2;
            }

            if(max != begin)
            {
                swap(a, max, begin);

                for(int i=begin; i>0 && a[i]>a[(int)((i-1)/2)]; i=(int)((i-1)/2))
                {
                    swap(a, i, (int)((i-1)/2));
                }
            }
        }

        swap(a, 0, end);
    }
}

int main(int argc, char* argv[])
{
    int a[]= {1,3,2,4,6,8,5,7};
    int len=sizeof(a)/sizeof(a[0]);
    sort(a, len);

    for(int i=0; i<len; i++)
    {
        printf("%d\t", a[i]);
    }
    printf("\n");

    return 0;
}